// Options
let sortingAlgorithm = quickSort; // bubbleSort, selectionSort, insertionSort, quickSort, mergeSort
let comparison = brightness; // brightness, red, green, blue
let imageSize = 250; // Make smaller for faster run time
let loops = 100; // # of times sorting algorithm runs before drawing (Higher number means larger changes)
let pixelDistance = 4; // Makes interesting visual effects (4 is correct value)
let url = 'https://ipfs.io/ipfs/bafybeihxzhlwsu5lkhzqu7sdlb5c43oinebfced5fdtk2zjgi3te2nbpb4/thunderstorm-3625405_1920.jpg';
// Global Variables
let imageLoaded = false;
let imgData;
let originalData;
let sortingCanvas;
let sortingCtx;
let imgHeight;
let imgWidth;
let keepSorting = true;
let sorted = false;
let animation;
let sSortIndex;
let stack;
let sortingAlgorithms = {
'bubble': bubbleSort,
'insertion': insertionSort,
'selection': selectionSort,
'merge': mergeSort,
'quick': quickSort
}
document.addEventListener("DOMContentLoaded", () => {
sortingCanvas = document.getElementById('sorting');
sortingCtx = sortingCanvas.getContext('2d');
function loadImage(url, callback) {
let img = new Image();
img.crossOrigin = 'Anonymous';
img.onload = function() {
let canvas = document.getElementById('canvas');
let ctx = canvas.getContext('2d');
let h = Math.min(imageSize, this.height);
let w = Math.round(this.width / this.height * h);
canvas.height = h;
canvas.width = w;
sortingCanvas.height = h;
sortingCanvas.width = w;
ctx.drawImage(this, 0, 0, w, h);
imgData = ctx.getImageData(0, 0, w, h);
var dataURI = canvas.toDataURL('png');
callback(dataURI, h, w, img);
}
img.src = url;
}
function afterLoad(URI, height, width, img) {
if (!imageLoaded) {
keepSorting = true;
imageLoaded = true;
img.src = URI;
imgHeight = height;
imgWidth = width;
console.log('Image loaded');
animation = window.requestAnimationFrame(draw);
}
}
loadImage(url, afterLoad);
document.getElementById('sorting-algorithm').addEventListener('change', (e) => {
sSortIndex = undefined
sortingAlgorithm = sortingAlgorithms[e.target.value];
if (imageLoaded) {
window.cancelAnimationFrame(animation)
stack = undefined;
imageLoaded = false;
keepSorting = true;
loadImage(url, afterLoad);
}
})
document.getElementById('image').addEventListener('change', (e) => {
window.cancelAnimationFrame(animation)
sSortIndex = undefined;
stack = undefined;
imageLoaded = false;
let image = e.target.files[0];
url = window.URL.createObjectURL(image);
document.getElementById('original-image').src = url;
loadImage(url, afterLoad);
})
})
function draw() {
if (keepSorting) {
sortHelper(sortingAlgorithm, imgData.data);
sortingCtx.putImageData(imgData, 0, 0);
window.requestAnimationFrame(draw);
} else {
console.log('Done sorting');
}
}
function sortHelper(sorter, array) {
switch (sorter.name) {
case "quickSort":
if (!stack) stack = quickSortHelper(array);
sorter(array, stack);
break;
case "mergeSort":
if (!stack) stack = mergeSortHelper(array);
sorter(array, stack);
break;
default:
sorter(array);
}
}
function bubbleSort(array) {
if (!sSortIndex) sSortIndex = array.length;
keepSorting = false;
for (let j = 0; j < loops; j++) {
for (let i = 0; i < sSortIndex; i += pixelDistance) {
if (comparison(array, i) > comparison(array, i + pixelDistance)) {
swapPixel(array, i, i + pixelDistance);
keepSorting = true;
}
}
sSortIndex -= pixelDistance;
}
return array;
}
function selectionSort(array) {
if (!sSortIndex) sSortIndex = array.length;
for (let j = 0; j < loops; j++) {
let max = -Infinity;
let ind;
for (let i = 0; i < sSortIndex; i += pixelDistance) {
if (comparison(array, i) > max) {
max = comparison(array, i);
ind = i;
}
}
swapPixel(array, ind, sSortIndex);
sSortIndex -= pixelDistance;
}
if (sSortIndex <= 3) keepSorting = false;
}
function insertionSort(array) {
if (!sSortIndex) sSortIndex = pixelDistance;
let currentIndex;
let newArray = array;
for (let i = 0; i < loops; i++) {
if (comparison(newArray, sSortIndex) < comparison(newArray, sSortIndex - pixelDistance)) {
currentIndex = sSortIndex - pixelDistance;
while (comparison(newArray, sSortIndex) < comparison(newArray, currentIndex)) {
if (currentIndex < 0) break;
currentIndex -= pixelDistance;
}
newArray = movePixel(newArray, sSortIndex, currentIndex + pixelDistance);
}
sSortIndex += pixelDistance;
}
newArray.forEach((e, i) => array[i] = e)
return array;
}
function quickSortHelper(array, qStack) {
if (!qStack) {
var qStack = [];
let splitPoint = split(array, 0, array.length - pixelDistance);
qStack.push({
split: splitPoint,
begin: 0,
end: splitPoint - pixelDistance
})
qStack.push({
split: splitPoint,
begin: splitPoint + pixelDistance,
end: array.length - pixelDistance
})
}
return qStack;
}
function quickSort(array, qStack) {
for (let i = qStack.length - 1; i >= 0; i--) {
let q = qStack[i];
if (q.begin < q.end && q.begin !== q.split && q.end !== q.split) {
let splitPoint = split(array, q.begin, q.end);
if (q.begin < splitPoint - pixelDistance)
qStack.push({
split: splitPoint,
begin: q.begin,
end: splitPoint - pixelDistance
})
if (q.begin + pixelDistance < q.end)
qStack.push({
split: splitPoint,
begin: splitPoint + pixelDistance,
end: q.end
})
}
qStack.splice(i, 1);
}
if (!qStack.length && sorted) keepSorting = false;
if (!qStack.length && !sorted) {
sorted = true;
stack = undefined;
}
return qStack;
}
function mergeSortHelper(array, s = 0, e = array.length - pixelDistance, mStack = []) {
if (s < e) {
let mid = floorToFour((e + s) / 2);
mergeSortHelper(array, s, mid, mStack);
mergeSortHelper(array, mid + pixelDistance, e, mStack);
mStack.unshift({
start: s,
mid: mid,
end: e
})
}
return mStack;
}
function mergeSort(array, mStack) {
let i = Math.min(loops, mStack.length);
while (i--) {
let m = mStack[mStack.length - 1];
merge(array, m.start, m.mid, m.end);
mStack.length--;
}
if (mStack.length === 0) keepSorting = false;
}
function merge(array, s, mid, e) {
let left = s,
right = mid + pixelDistance,
merged = [];
while (left <= mid && right <= e) {
if (comparison(array, left) < comparison(array, right)) {
merged.push(...getPixels(array, left));
left += pixelDistance;
} else {
merged.push(...getPixels(array, right));
right += pixelDistance;
}
}
while (left <= mid) {
merged.push(...getPixels(array, left));
left += pixelDistance;
}
while (right <= e) {
merged.push(...getPixels(array, right));
right += pixelDistance;
}
combine(array, merged, s);
return array;
}
// Helper Functions
function combine(array, copy, s) {
for (let i = 0; i < copy.length; i++) {
array[i + s] = copy[i];
}
return array;
}
function split(array, start, end) {
let done = false,
left = start + pixelDistance,
right = end,
pivot = comparison(array, start);
while (!done) {
while (left <= right && comparison(array, left) <= pivot) left += pixelDistance;
while (comparison(array, right) >= pivot && right >= left) right -= pixelDistance;
if (left >= right) done = true;
else swapPixel(array, left, right);
}
swapPixel(array, start, right);
return right;
}
function swapPixel(array, i1, i2) {
for (let i = 0; i < 3; i++) {
let t = array[i1 + i];
array[i1 + i] = array[i2 + i];
array[i2 + i] = t;
}
return array;
}
function movePixel(array, initial, end) {
let toMove = array.slice(initial, initial + pixelDistance);
let newArray;
if (initial > end) {
newArray = [...array.slice(0, end), ...toMove, ...array.slice(end, initial), ...array.slice(initial + pixelDistance)];
} else {
newArray = [...array.slice(0, initial), ...array.slice(initial + pixelDistance, end + pixelDistance), ...toMove, ...array.slice(end + pixelDistance)];
}
return newArray;
}
function getPixels(array, i) {
return [array[i], array[i + 1], array[i + 2], array[i + 3]]
}
function floorToFour(num) {
return Math.floor(num / 4) * 4;
}
// Comparison functions
function brightness(array, index) {
return array[index] + array[index + 1] + array[index + 2];
}
function red(array, index) { return array[index]; }
function green(array, index) { return array[index + 1]; }
function blue(array, index) { return array[index + 2]; }